package offer.day35;

public class No60PrintProbability {
    /*
     * 面试题60：n个骰子的点数
     * 题目：把n个骰子扔到地上，所有骰子朝上一面的点数之和为s。
     * 输入n，打印出s的所有可能的值出现的概率
     *
     * 需要先统计出每个点数出现的次数，然后再每个点出现的次数除以6的n次方
     * （n个骰子所有点数的排列数），就是每个点数出现的概率
     * 思路：运用循环的思想，时间性能好O(n)
     * 首先构建两个数组存储骰子点数的每个总数s出现的次数
     * 第一次循环：第一个数组中的第n个数字表示：骰子和为n出现的次数
     * 第二次~第n次循环：因为分析发现f(n)和为n的骰子出现的次数
     * =上一轮循环中骰子和为n-1，n-2，n-3，n-4，n-5，n-6的次数的总和
     * 所以从第二次开始每一次都要加上前一个数组的n-1到n-6的值
     * 其中使用flag对两个数组进行切换  且要保证每次进行切换时数据都经过了清零操作
     *
     * 程序中使用maxValue这一变量来存储骰子面数6，是为了当其他厂家使用其他点数的骰子时，
     * 只需要更改maxValue的值即可，对程序的扩展性极好
     * */


    public static void main(String[] args) {
        No60PrintProbability p = new No60PrintProbability();
        int n = 6;//骰子个数
        System.out.println("打印出所有的骰子点数的概率（骰子点数及其出现的概率）");
        p.PrintProbability(n);
    }

    int maxValue=6;
    private void PrintProbability(int n) {
        if(n<1) return;
        //初始化
        int[][] pProbability=new int[2][maxValue*n+1];
        for(int i=0;i<maxValue*n+1;i++){
            pProbability[0][i]=0;
            pProbability[1][i]=0;
        }

        int flag=0;
        for(int i=1;i<=maxValue;i++){
            pProbability[0][i]=1;
        }
        for(int k=2;k<=n;k++){
            for(int i=0;i<k;i++){
                pProbability[1-flag][i]=0;
            }
            for(int i = k; i <= maxValue*k;i++) {
                pProbability[1-flag][i] = 0;
                for(int j = 1;j <= i && j <= maxValue;++j)
                    //也就是【i】 = 【j】 + 【i-j】
                    pProbability[1-flag][i] += pProbability[flag][i-j];
            }
            flag = 1 - flag;
        }
        //算出概率并打印
        //Java中使用Math类的pow方法：
        //public static double pow(double a,double b),
        //返回第一个参数的第二个参数次幂的值
        double total = Math.pow((double)maxValue,n);
        System.out.println(total);
        for(int i = n;i <= maxValue*n;i++) {
            double ratio = (double)pProbability[flag][i]/total;
            System.out.println(i+":"+ratio);
        }
    }
}
